package code.class3;
/**
 * https://leetcode.cn/problems/trapping-rain-water/
 * 接雨水问题
 */
public class Code04_trapTrain {
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 3, 9, 2, 4, 6, 8, 4, 2, 1};
        int trap = trap(arr);
        System.out.println("trap = " + trap);
    }

    /**
     *  	      0
     *            0       0
     *            0       0
     *        0   0     0 0
     *  0     0   0     0 0
     *  0   0 0   0   0 0 0 0
     *  0   0 0 0 0   0 0 0 0
     *  0 0 0 0 0 0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0 0 0 0 0 0 0
     *  0 1 2 3 4 5 6 7 8 9 a b c
     * * 从 1 位置开始计算，
     * 1.a左边和右边最大值最小的那个，为瓶颈
     * 2.取瓶颈值 减 底座高度，如果为负数，则水量为0
     * 3.如果不为0，则就是该位置存水量
     *
     */
    public static int trap(int[] arr) {
        int n = arr.length;
        int[] lmax = new int[n];
        int[] rmax = new int[n];
        lmax[0] = arr[0]; // 左侧第0位置
        // 从左 -> 右 ,找到左边最大值
        for (int i = 1; i < arr.length; i++) {
            lmax[i] = Math.max(lmax[i - 1], arr[i]);
        }
        rmax[n - 1] = arr[n - 1];// 右侧第n-1位置
        // 从左 -> 右 ,找到左边最大值
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], arr[i]);
        }
        int ans = 0;
        // 开始计算雨量
        for (int i = 1; i < n - 1; i++) {
            ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - arr[i]);
        }
//        ArrayUtils.printArr(lmax);
//        ArrayUtils.printArr(rmax);
//        ArrayUtils.printArr(arr);
//        ArrayUtils.printArr(ans);
        return ans;
    }
}
